A number of systems and programs are offered on the market for the design, the engineering and the manufacturing of objects. CAD is an acronym for Computer-Aided Design, e.g. it relates to software solutions for designing an object. CAE is an acronym for Computer-Aided Engineering, e.g. it relates to software solutions for simulating the physical behavior of a future product. CAM is an acronym for Computer-Aided Manufacturing, e.g. it relates to software solutions for defining manufacturing processes and operations. In such computer-aided design systems, the graphical user interface plays an important role as regards the efficiency of the technique. These techniques may be embedded within Product Lifecycle Management (PLM) systems. PLM refers to a business strategy that helps companies to share product data, apply common processes, and leverage corporate knowledge for the development of products from conception to the end of their life, across the concept of extended enterprise. The PLM solutions provided by Dassault Systèmes (under the trademarks CATIA, ENOVIA and DELMIA) provide an Engineering Hub, which organizes product engineering knowledge, a Manufacturing Hub, which manages manufacturing engineering knowledge, and an Enterprise Hub which enables enterprise integrations and connections into both the Engineering and Manufacturing Hubs. All together the system delivers an open object model linking products, processes, resources to enable dynamic, knowledge-based product creation and decision support that drives optimized product definition, manufacturing preparation, production and service.
In this context and other contexts, much research has been performed on image completion. Image completion designates algorithms for completing an image having at least one hole. Image completion includes image inpainting, which designates image completion where the at least one hole is(are) relatively small. Image completion of relatively large holes may be a more difficult problem to solve than image inpainting. Indeed, image inpainting is akin to interpolation, where one can only extrapolate the value of the surrounding pixels.
Image completion is useful in different contexts, including in all image retouching applications in which part of the image has been removed and, for example, a user needs to fill in the removed part. This includes applications in which one wants to move an object in an image, or one wants to replace an object in an image with something else. More generally image completion can be useful in any situation where one wants to fill in missing data and the data is organized as a contiguous 2D array (matrix form), or more generally as a contiguous ND array.
Three known categories of image completion can be identified:                A. PDE-based methods        B. Statistically-based methods        C. Exemplar-based methods        
A. PDE-Based Methods
PDE-based methods were first introduced for image inpainting where the holes often come from crackles, creases, artifacts or reflects. These methods consider filling the void that is left by propagating the information from the edges of the void. The information is propagated using partial differential equations that are solved on a pixel level. Such equations include propagation equations such as the heat equation. These methods often use Laplace's PDE with Dirichlet boundary conditions or simulate an anisotropic diffusion process. While pure diffusion methods result in blurred completion, some algorithms have been designed to preserve the edges.
Examples of PDE-based methods can be found in the following papers:                Bertalmio, Marcelo, Andrea L. Bertozzi, and Guillermo Sapiro. Navier-stokes, fluid dynamics, and image and video inpainting. CVPR. 2001        Chan, Tony F., and Jianhong Shen. Nontexture inpainting by curvature-driven diffusions. Journal of Visual Communication and Image Representation. 2001        Auroux, Didier, and Mohamed Masmoudi. A one-shot inpainting algorithm based on the topological asymptotic analysis. Computational & Applied Mathematics. 2006        Pietro Perona and Jitendra Malik. Scale-space and edge detection using anisotropic diffusion. IEEE Trans. 1990        Ivars Peterson. Filling in blanks: Automating the restoration of a picture's missing pieces. Science News. 2002        
B. Statistically-Based Methods
Statistically-based methods are mainly used for the case of texture (i.e. repetitive pattern in an image) synthesis. Most of natural pictures are formed of a patchwork of textures (e.g. in the case of a picture of a person on a grassy field, the grassy field can be seen as a texture). Textures are seemingly random, and texture synthesis aims at achieving a degree of randomness that is pleasing to the eye. These methods are composed of two steps:                1) Learning step: Given an input texture, the methods try to describe it by extracting relevant statistics through the use of compact parametric statistical models. This compact statistical model is often based on wavelet coefficients and can combine a multi-scale approach.        2) Diffusion step: The texture is grown inwards to complete the unknown region. Statistically based methods generally fail for the problem of image completion where structures in the image can be found, because structure is not random.        
Examples of statistically-based methods can be found in the following papers:                Portilla, Javier, and Eero P. Simoncelli. A parametric texture model based on joint statistics of complex wavelet coefficients. IJCV. 2000        Heeger, David J., and James R. Bergen. Pyramid-based texture analysis/synthesis. SIGGRAPH. 1995        Li-Yi Wei and Marc Levoy. Fast texture synthesis using tree-structured vector quantization. SIGGRAPH, pages 479-488. 2000        
C. Exemplar-Based Methods
In exemplar-based methods, the void left is filled using existing image patches. Roughly speaking this consists in copying parcels of the image and pasting them inside the void. The way the hole is filled with these patches differs according to the method chosen. Most of exemplar-based methods can be associated to one of the three following classes:                1) Inwards diffusion methods: The earliest methods complete the void iteratively. In paper “Criminisi, Pérez, and Toyama. Region filling and object removal by exemplar-based image inpainting. IEEE Transactions on Image Processing. 2004”, the void is filled from the outer edge inwards with small patches, once the first outer ring is patched, the algorithm starts again as if the void was smaller, until the void is patched up. Another example can be found in paper “Xiaowu Chen, Bin Zhou, Fang Xu, and Qinping Zhao. Automatic image completion with structure propagation and texture synthesis. 2010”. Unfortunately, these algorithms are often stuck because of bad choices on the borders that make the completion of the center impossible.        2) Matching-based methods: These methods are often related to texture models and use patch reinjection. They iteratively try to improve the current filling by replacing a patch in the unknown region with a known patch (often taken as the nearest patch in the extracted collection). In paper “Drori, Iddo, Daniel Cohen-Or, and Hezy Yeshurun. Fragment-based image completion. ACM Transactions on Graphics. 2003”, the void is filled by starting at low scales where the void can be seen as a small hole that can be patched by only one image patch and then working the way up to full resolution from the previous image, and finding patches that match the filling that was made at the previous resolution. Similar approaches can be found in paper “Alexei A. Efros and Thomas K. Leung. Texture synthesis by non-parametric sampling. ICCV, pages 1033-1038. 1999” and paper “Yonatan Wexler, Eli Shechtman, and Michal Irani. Space-time video completion. CVPR (1), pages 120-127. 2004”. These methods also suffer from an important flaw: during the iteration, if one step fails, then the result is completely off. Phantom parts of the image can thus be copied inside the void resulting in images that are not realistic.        3) Statistical Offsets Analysis methods: These methods learn the main displacements in the image, through a statistical model, and use this knowledge to fill the missing part. Examples of this kind of methods can be found in paper “Kaiming He and Jian Sun. Computing nearest-neighbor fields via propagation-assisted kd-trees. IEEE Conference on Computer Vision and Pattern Recognition. 2012” and paper “Kaiming He and Jian Sun. Statistics of patch offsets for image completion. Computer Vision—ECCV. 2012”. These methods perform correctly when the image contains structural regularities (as for example in architecture images), but often fail drastically on general images.        
A famous example of an exemplar-based approach is the algorithm called Patch-Match disclosed in paper “Connelly Barnes, Eli Shechtman, Adam Finkelstein, and Dan B. Goldman. Patch-match: a randomized correspondence algorithm for structural image editing. ACM Trans. Graph., 28(3), 2009”. This algorithm has been highly popularized by its use in Adobe Photoshop™ Content Fill Aware. In practice, this heuristic is simple to implement, but it is not robust.
Within this context, there is still a need for an improved way of completing an image having at least one hole.